{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Move Sub-Tree of N-Ary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: moveSubTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移动 N 叉树的子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵没有重复值的 <span data-keyword=\"n-ary-tree\">N 叉树</span> 的根节点&nbsp;<code>root</code>&nbsp;，以及其中的两个节点&nbsp;<code>p</code> 和&nbsp;<code>q</code>。</p>\n",
    "\n",
    "<p>移动节点&nbsp;<code>p</code>&nbsp;及其子树，使节点 <code>p</code>&nbsp;成为节点&nbsp;<code>q</code>&nbsp;的直接子节点。如果&nbsp;<code>p</code>&nbsp;已经是&nbsp;<code>q</code>&nbsp;的直接子节点，则请勿改动任何节点。节点&nbsp;<code>p</code> <strong>必须</strong>是节点&nbsp;<code>q</code>&nbsp;的子节点列表的最后一项。</p>\n",
    "\n",
    "<p>返回改动后的<em>树的根节点</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>节点&nbsp;<code>p</code>&nbsp;和&nbsp;<code>q</code>&nbsp;可能是下列三种情况之一：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>节点&nbsp;<code>q</code>&nbsp;在节点&nbsp;<code>p</code>&nbsp;的子树中。</li>\n",
    "\t<li>节点&nbsp;<code>p</code>&nbsp;在节点&nbsp;<code>q</code>&nbsp;的子树中。</li>\n",
    "\t<li>节点&nbsp;<code>p</code>&nbsp;不在节点&nbsp;<code>q</code>&nbsp;的子树中，且节点&nbsp;<code>q</code> 也不在节点&nbsp;<code>p</code>&nbsp;的子树中。</li>\n",
    "</ol>\n",
    "\n",
    "<p>在第 2 种和第 3 种情况中，你只需要移动&nbsp;<code>p</code>&nbsp;（及其子树），使 <code>p</code>&nbsp;成为&nbsp;<code>q</code>&nbsp;的子节点。但是在第 1 种情况中，树的节点可能会断连，因此你还需要重新连接这些节点。<strong>请在解题前仔细阅读示例。</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><em>N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔（见示例）。</em></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png\" style=\"height: 269px; width: 296px;\" /></p>\n",
    "\n",
    "<p>例如，上面的树会被序列化为&nbsp;[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/13/move_e1.jpg\" style=\"height: 188px; width: 450px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 4, q = 1\n",
    "<strong>输出:</strong> [1,null,2,3,4,null,5,null,6,null,7,8]\n",
    "<strong>解释:</strong> 该示例属于第二种情况，节点 p 在节点 q 的子树中。我们可以移动节点 p 及其子树，使 p 成为节点 q 的直接子节点。\n",
    "注意，节点 4 是节点 1 的最后一个子节点。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/13/move_e2.jpg\" style=\"height: 281px; width: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 7, q = 4\n",
    "<strong>输出:</strong> [1,null,2,3,null,4,5,null,6,null,7,8]\n",
    "<strong>解释:</strong> 节点 7 已经是节点 4 的直接子节点，因此我们不改动任何节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/13/move_e3.jpg\" style=\"height: 331px; width: 450px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 3, q = 8\n",
    "<strong>输出:</strong> [1,null,2,null,4,5,null,7,8,null,null,null,3,null,6]\n",
    "<strong>解释:</strong> 该示例属于第三种情况，节点 p 不在节点 q 的子树中，反之亦然。我们可以移动节点 3 及其子树，使之成为节点 8 的子节点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的总数在&nbsp;<code>[2,&nbsp;1000]</code>&nbsp;间。</li>\n",
    "\t<li>每个节点都有&nbsp;<strong>唯一&nbsp;</strong>的值。</li>\n",
    "\t<li><code>p != null</code></li>\n",
    "\t<li><code>q != null</code></li>\n",
    "\t<li><code>p</code>&nbsp;和&nbsp;<code>q</code>&nbsp;是两个不同的节点（即&nbsp;<code>p != q</code>&nbsp;）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [move-sub-tree-of-n-ary-tree](https://leetcode.cn/problems/move-sub-tree-of-n-ary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [move-sub-tree-of-n-ary-tree](https://leetcode.cn/problems/move-sub-tree-of-n-ary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,3,null,4,5,null,6,null,7,8]\\n4\\n1', '[1,null,2,3,null,4,5,null,6,null,7,8]\\n7\\n4', '[1,null,2,3,null,4,5,null,6,null,7,8]\\n3\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        mp = {}\n",
    "        queue = [root]\n",
    "        mp[root.val] = None\n",
    "        while queue:\n",
    "            nq = []\n",
    "            for x in queue:\n",
    "                for ch in x.children:\n",
    "                    mp[ch.val] = x\n",
    "                    nq.append(ch)\n",
    "            queue = nq\n",
    "        #case 2\n",
    "        if mp[p.val] == q:\n",
    "            return root\n",
    "        x = q\n",
    "        while x and mp[x.val] != p:\n",
    "            x = mp[x.val]\n",
    "\n",
    "        #case 3\n",
    "        if not x:\n",
    "            q.children.append(p)\n",
    "            mp[p.val].children.remove(p)\n",
    "            return root\n",
    "        #case 1\n",
    "        # print(f'{mp[p.val].val, q.val}')\n",
    "        mp[q.val].children.remove(q)\n",
    "        pa = mp[p.val]\n",
    "        if not pa:\n",
    "            q.children.append(p)\n",
    "            return q\n",
    "        n = len(pa.children)\n",
    "        for i in range(n):\n",
    "            if pa.children[i] == p:\n",
    "                pa.children[i] = q\n",
    "                q.children.append(p)\n",
    "                break\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        def isSubTree(n1, n2):#return if n2 is subtree of n1\n",
    "            for child in n1.children:\n",
    "                if child == n2:\n",
    "                    return True\n",
    "                elif isSubTree(child, n2):\n",
    "                    return True\n",
    "            return False\n",
    "        def deleteChild(parent, target):\n",
    "            for child in parent.children:\n",
    "                if child == target:\n",
    "                    parent.children.remove(target)\n",
    "                    return\n",
    "                else:\n",
    "                    deleteChild(child, target)\n",
    "        def isDirectChild(parent, target):\n",
    "            for n in parent.children:\n",
    "                if n == target: return True\n",
    "            return False\n",
    "        def replaceChild(node, ori, target):\n",
    "            for i, child in enumerate(node.children):\n",
    "                if child == ori:\n",
    "                    node.children[i] = target\n",
    "                    return\n",
    "                else:\n",
    "                    replaceChild(child, ori, target)\n",
    "\n",
    "        if isSubTree(p, q): #case 1\n",
    "            print(\"#case1\")\n",
    "            deleteChild(p, q)\n",
    "            q.children.append(p)\n",
    "            if p == root: return q\n",
    "            else: #replace the child p with q for parent\n",
    "                # print(p, q)\n",
    "                replaceChild(root, p, q)\n",
    "            return root\n",
    "                \n",
    "        elif isSubTree(q, p):\n",
    "            if isDirectChild(q, p): return root           \n",
    "            deleteChild(q, p)\n",
    "            q.children.append(p)\n",
    "            print('#case2')\n",
    "            return root\n",
    "        else:\n",
    "            deleteChild(root, p)\n",
    "            q.children.append(p)\n",
    "            print('#case3')\n",
    "            return root\n",
    "        #  1\n",
    "        # 2  3\n",
    "        #4 5  6\n",
    "        #78\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        if self.isSubTree(q, p): #case 1: q is a subtree of p\n",
    "            parentP = self.parent(root, p)\n",
    "            parentQ = self.parent(root, q)\n",
    "            parentQ.children.remove(q)\n",
    "            q.children.append(p)\n",
    "            if parentP: # p is not the root\n",
    "                index = parentP.children.index(p)\n",
    "                parentP.children.remove(p)\n",
    "                parentP.children.insert(index, q)\n",
    "                return root\n",
    "            return q # p is the root\n",
    "        #case 2,3\n",
    "        parentP = self.parent(root, p)\n",
    "        if parentP is q:\n",
    "            return root\n",
    "        parentP.children.remove(p)\n",
    "        q.children.append(p)\n",
    "        return root\n",
    "\n",
    "    def isSubTree(self, p, q): # whether p is a subtree of q\n",
    "        if not q.children: return False\n",
    "        if p in q.children: return True\n",
    "        res = False\n",
    "        for child in q.children:\n",
    "            res = res or self.isSubTree(p, child)\n",
    "        return res\n",
    "\n",
    "    def parent(self, root, p): # find the parent of p\n",
    "        if not root: return None\n",
    "        if p in root.children:\n",
    "            return root\n",
    "        res = None\n",
    "        for child in root.children:\n",
    "            res = res or self.parent(child, p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        def dfs(node1, node2):\n",
    "            if node1 is None:\n",
    "                return False\n",
    "            if node1 == node2:\n",
    "                return True\n",
    "            k = -1\n",
    "            for i in range(len(node1.children)):\n",
    "                if node1.children[i] == node2:\n",
    "                    k = i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                node1.children.pop(k)\n",
    "                return True\n",
    "            for i in range(len(node1.children)):\n",
    "                if dfs(node1.children[i], node2):\n",
    "                    return True\n",
    "            return False\n",
    "        def dfs2(node0, node1, node2):\n",
    "            if node0 is None:\n",
    "                return False\n",
    "            if node0 == node1:\n",
    "                return True\n",
    "            k = -1\n",
    "            for i in range(len(node0.children)):\n",
    "                if node0.children[i] == node1:\n",
    "                    k = i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                node0.children[k] = node2\n",
    "                return True\n",
    "            for i in range(len(node0.children)):\n",
    "                if dfs2(node0.children[i], node1, node2):\n",
    "                    return True\n",
    "            return False\n",
    "        if dfs(p, q):\n",
    "            q.children.append(p)\n",
    "            x = Node(0, [root])\n",
    "            dfs2(x, p, q)\n",
    "            return x.children[0]\n",
    "        else:\n",
    "            for i in q.children:\n",
    "                if i == p:\n",
    "                    return root\n",
    "            dfs(root, p)\n",
    "            q.children.append(p)\n",
    "            return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        dummy=Node()\n",
    "        dummy.children.append(root)\n",
    "        pParent,qParent,is_p_over_q=None,None,False\n",
    "        def dfs(node,parent,is_under_p):\n",
    "            nonlocal pParent,qParent,is_p_over_q\n",
    "            if node==p:\n",
    "                pParent,is_under_p=parent,True\n",
    "            if node==q:\n",
    "                if is_under_p:\n",
    "                    is_p_over_q=True                \n",
    "                qParent=parent\n",
    "            for child in node.children:\n",
    "                dfs(child,node,is_under_p)\n",
    "        dfs(root,dummy,False)\n",
    "        if pParent==q:\n",
    "            return root\n",
    "        if is_p_over_q:\n",
    "            qParent.children.remove(q)\n",
    "            idx=pParent.children.index(p)\n",
    "            pParent.children[idx]=q\n",
    "            q.children.append(p)\n",
    "        else:\n",
    "            pParent.children.remove(p)\n",
    "            q.children.append(p)\n",
    "        return dummy.children[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        dummy=Node()\n",
    "        dummy.children.append(root)\n",
    "        pParent,qParent,is_p_over_q=None,None,False\n",
    "        def dfs(node,parent,is_under_p):\n",
    "            nonlocal pParent,qParent,is_p_over_q\n",
    "            if node==p:\n",
    "                pParent,is_under_p=parent,True\n",
    "            if node==q:\n",
    "                if is_under_p:\n",
    "                    is_p_over_q=True                \n",
    "                qParent=parent\n",
    "            for child in node.children:\n",
    "                dfs(child,node,is_under_p)\n",
    "        dfs(root,dummy,False)\n",
    "        if pParent==q:\n",
    "            return root\n",
    "        if is_p_over_q:\n",
    "            qParent.children.remove(q)\n",
    "            idx=pParent.children.index(p)\n",
    "            pParent.children[idx]=q\n",
    "            q.children.append(p)\n",
    "        else:\n",
    "            pParent.children.remove(p)\n",
    "            q.children.append(p)\n",
    "        return dummy.children[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def moveSubTree(self, root: 'Node', p: 'Node', q: 'Node') -> 'Node':\n",
    "        self.pParent = None \n",
    "        self.qParent = None\n",
    "        self.pOverq = False \n",
    "        def dfs(node, par, foundP):\n",
    "            if node == p:\n",
    "                self.pParent = par \n",
    "                foundP = True \n",
    "            if node == q:\n",
    "                self.qParent = par \n",
    "                if foundP:\n",
    "                    self.pOverq = True \n",
    "            for child in node.children:\n",
    "                dfs(child, node, foundP)\n",
    "        dummy = Node(0, [])\n",
    "        dummy.children.append(root)\n",
    "        dfs(root, dummy, False)\n",
    "        if self.pParent == q:\n",
    "            return root \n",
    "        if self.pOverq:\n",
    "            idx = self.pParent.children.index(p)\n",
    "            self.qParent.children.remove(q)\n",
    "            self.pParent.children[idx] = q \n",
    "            q.children.append(p)\n",
    "        else:\n",
    "            self.pParent.children.remove(p)\n",
    "            q.children.append(p)\n",
    "        return dummy.children[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
